package algorithm.dynamic_programming;



public class BobDie {

    public static double livePosibility1(int row, int col, int k, int N, int M){
        if(N == 0 || M == 0 || k == 0)
            return 0;
        int i = process(row, col, k, N, M);
        return i/Math.pow(4, k);
    }

    public static int process(int row, int col, int rest, int N, int M){
        if(row >= N || row < 0 || col >= M || col < 0)
            return 0;
        if(rest == 0)
            return 1;
        int result = 0;
        result += process(row, col - 1, rest - 1, N, M) +
                process(row, col + 1, rest - 1, N, M) +
                process(row + 1, col, rest - 1, N, M) +
                process(row - 1, col, rest - 1, N, M);
        return result;
    }

    public static double livePosibility2(int row, int col, int k, int N, int M){
        if(N == 0 || M == 0 || k == 0)
            return 0;
        int[][][] dp = new int[N][M][k + 1];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                dp[i][j][0] = 1;
            }
        }
        for (int rest = 1; rest <= k; rest++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    dp[i][j][rest] = pick(i, j - 1, rest - 1, N, M, dp) +
                            pick(i, j + 1, rest - 1, N, M, dp) +
                            pick(i - 1, j, rest - 1, N, M, dp) +
                            pick(i + 1, j, rest - 1, N, M, dp);
                }
            }
        }
        return dp[row][col][k]/Math.pow(4, k);
    }

    public static int pick(int row, int col, int rest, int N, int M, int[][][] dp){
        if(row >= N || row < 0 || col >= M || col < 0)
            return 0;
        return dp[row][col][rest];
    }


    public static void main(String[] args) {
//        System.out.println(livePosibility1(6, 6, 10, 10, 10));
        System.out.println(livePosibility2(6, 6, 10, 20, 20));
    }
}
